package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.分治;

import com.zp.self.module.level_4_算法练习.数据结构.二叉树.TreeNode;

/**
* @author  ZengPeng
**/
public class 力扣_108_将有序数组转换为二叉搜索树 {
    public static void main(String[] args) {
        TreeNode treeNode = new 力扣_108_将有序数组转换为二叉搜索树().sortedArrayToBST(new int[]{-10, -3, 0, 5, 9});
        System.out.println(treeNode);
    }

    /**
       题目： 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
                高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

       分析：
            1.二分法  中间的为中节点，小的为左节点，大的为右节点
                递归组装节点? 这需要循环创建数组,内存消耗大。while循环组装节点？
                判断条件：什么时候继续循环或者递归？middle>left   middle<right 时继续
                循环不变量： [left,right] 范围的数据是需要插入的

       边界值注意：
            1.middle ==left
     **/
    public TreeNode sortedArrayToBST(int[] nums) {
        return recursive(nums,0,nums.length-1);
    }

    private  TreeNode recursive(int[] nums,int left,int right){
        int middle = left+((right-left)>>1);
        TreeNode middleNode= new TreeNode();
        middleNode.val = nums[middle];
        if(left<middle)
            middleNode.left = recursive(nums,left,middle-1);// 循环不变量： [left,right] 范围的数据是需要插入的
        if(right>middle)
            middleNode.right = recursive(nums,middle+1,right);// 循环不变量： [left,right] 范围的数据是需要插入的
        return   middleNode;
    }
}
